All Questions
12 questions
0votes
0answers
102views
Understanding a remark on O(log d) ratio for Online Set Cover
In the paper "The Online Set Cover Problem" by Alon, Awerbuch, Azar, Buchbinder and Naor, they study an online version of the set cover problem in which elements arrive one by one and ...
- 649
3votes
0answers
159views
Exactly solvable but non-trivial integrality gap
Are there interesting polynomial time solvable problems that we know of for which the natural convex relaxation has a non-trivial integrality gap? Note: Maximum matching doesn't qualify because I ...
- 7,060
11votes
1answer
1kviews
Why is complementary slackness important?
Complementary slackness (CS) is commonly taught when talking about duality. It establishes a nice relation between the primal and the dual constraint/variables from a mathematical viewpoint. The two ...
- 5,415
2votes
0answers
81views
General covering approximation
Consider the following integer program (general covering): $\min c \cdot x$ subject to $Ax \ge b$, where all entries in $A, b, c$ are nonnegative and $x$ is required to be nonnegative and integral. ...
- 233
1vote
1answer
331views
Approximation algorithm for graph problem
In the process of trying to create an approximation algorithm for the following problem. Let $G = (V,E)$ be a graph, $c_e, c_{iv} \ge 0$, for $e \in E$, $i \in L$, and $v \in V$, where $L$ is a ...
- 233
5votes
0answers
259views
On the optimal solution of the CKR formulation for MULTIWAY CUT
Currently the best approximation algorithm for the MULTIWAY CUT problem is obtained via the linear program based on geometrical embedding by CKR [1]. Let $U_i$ be those vertices in $V-T$ which is ...
- 2,579
3votes
1answer
2kviews
Max-cut via linear programming or sdp
I am looking for a linear programming formulation for the max-cut problem. My interest is to know about the primal - dual algorithm for max-cut. It would be nice if someone can tell me that what is ...
- 735
19votes
3answers
2kviews
Integrality gap and approximation ratio
When we consider an approximation algorithm for a minimization problem, the integrality gap of an IP formulation for this problem gives a lower bound of an approximation ratio for certain class of ...
- 1,200
37votes
1answer
2kviews
Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers
I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional "...
- 4,962
10votes
1answer
244views
Relaxing $\ell_0$ constraints in an optimization
I have a feasibility question that can be framed as follows. I'm given a point $p$ in a $d$-dimensional vector space, and I want to find the closest point $q$ to $p$ that satisfies a set of "$\ell_0$ ...
- 32.3k
20votes
1answer
431views
What are the best possible time/error tradeoffs for approximate solution of linear programs?
For concreteness consider the LP for solving a two-player zero-sum game where each player has $n$ actions. Suppose each entry of the payoff matrix $A$ is at most 1 in absolute value. For simplicity ...
- 1,884
51votes
8answers
10kviews
The importance of Integrality Gap
I always had trouble in understanding the importance of the Integrality Gap (IG) and bounds on it. IG is the ratio of (the quality of) an optimal integer answer to (the quality of) an optimal real ...
- 21.9k
